2022 Algorithm                 < No.4 Time Bomb>                         Prof. Zoh

시한폭탄

[문제]   N개의 화물 운송용 컨테이너 박스 중 하나에 시한폭탄이 장착되어 있다는 첩보가 수집되었다. 우리는 최대한 이른 시간에 이 문제의 박스를 찾아서 제거해야만 한다. 또 다른 첩보에 따르면 이 시한폭탄은 전체 N개의 박스 중에서 2번째로 무거운 박스에 들어있다고 한다. 문제는 각 박스의 크기가 너무 커서 일반적인 화물 저울로는 그 무게를 잴 수가 없다. 우리가 단지 할 수 있는 것은 두 박스 [eqn: B[i]]와 [eqn: B[j]]를 커다란 시소(seas aw) 같은 장치에 올려 둘 중 어떤 것이 “더 무거운”지만을 계산할 수 있다. 즉 어느 쪽이 더 기우는지를 확인하여 둘 중 더 무거운 박스가 어떤 것인지만을 알 수 있다. 그런데 이 한 번의 비교 작업에도 상당한 시간이 걸려 우리는 최소한의 비교만으로 두 번째로 무거운 박스를 찾아내어야 한다. 시간이 지체되면 시한폭탄이 폭발할 수 있으므로 최대한 시간을 아껴야 한다. 이번 문제는 내장된 함수의 호출을 이용해서 풀어야 한다.

먼저 이 문제를 풀기 위하여 아래와 같이 시작할 때 timebomb.h를 include 시켜야 한다. 이 헤더 함수에 여러분이 사용할 모든 함수가 내장되어 있다. 제일 먼저 box_ready( )를 호출하여 데이터를 준비해야 한다. 그 다음 box_num( )를 불러 전체 박스의 개수가 확인한다. 박스는 1부터는 N번까지 순차적인 번호로 표시된다. 즉 [eqn: B[1]]부터 [eqn: B[N]]까지 준비되어 있다.

여러분은 선택한 두 박스, [eqn: B[i]]와 [eqn: B[j]]의 무게 비교 결과를 box_comp(i,j)함수를 사용하여 로 알아낼 수 있다. 단 이 문제는 모든 박스의 무게는 서로 다르다고 가정한다. 그 값이 1이면 [eqn: B[i]] > [eqn: B[j]], -1이면 [eqn: B[i]] < [eqn: B[j]], 그외 경우, 예를 들어 [eqn: i,j]가 범위를 벗어난다든지 하면 숫자 0이 return된다. 그리고 최종 확인된 시한 폭탄이 담긴 박스의 index [eqn: this]를 함수 box_report( this )를 사용하여 보고한다. 이 함수가 호출되면 프로그램은 종료된다.

#include "timebomb.h"    // 0. 반드시 포함

. . .

int main( ) {

int N, result, this ;

. . . .

box_ready( ) ;     // 1. 제일 먼저 호출해야 함.

N = box_num( ) ;   // 2. 갯수 확인.

. . . .

result = box_comp( i, j ) // 무게 비교 작업

. . . . .

box_report( this ) ;  // 정답 보고, 종료됨

} // end of main( )

단 이 문제에서 여러분은 box_comp(i,j) 함수의 호출을 일정 이상 할 수 없다. 각 test case마다 정해진 기준 이상으로 호출하게 되면 틀린 답으로 간주된다.

[입출력]   이번 문제에서 입출력은 header file에서 모두 처리하므로 여러분은 이 문제에 대하여 신경 쓸 필요는 없다. [eqn: N]의 범위는 [eqn: 10` LEQ `N` leq 5000] 이며 box_comp(i,j) 함수의 허용 호출 횟수는 박스의 개수를 N이라고 했을 때 최대 [eqn: b(N) = N + LCEIL \log _ { `` 2} ``N RCEIL + 1] 번 까지 허용된다.

[eqn: LCEIL x RCEIL]는 ceiling 함수로서 예를 들면[eqn: LCEIL 9.2 RCEIL]= 10, [eqn: LCEIL 5.0 RCEIL]= 5, [eqn: LCEIL 12.941 RCEIL]= 13 이다.

[예제]	제공되는 "timebomb.h"는  여러분의 이해를 돕고 연습을 하기 위하여 구성된 것이며 실제 평가를 할 때에는 제공된 것과 다른 것을 사용한다. 즉 위 header file에서 사용되는 변수나 호출 구조를 여러분은 알 수 없으며, 앞서 설명한 함수만을 호출하여 답을 구해야 한다.

[제한조건]  이번 문제는 c/c++로만 제출할 수 있다.  최대 허용 제출횟수는 20회, 각 데이터 당 제한시간은 1초이다. 과제 마감시간과 제출 시작 시간, 최대 제출 횟수, 수행시간(CPU time), 제출 프로그램의 최대 크기는 NESPA를 확인하기 바란다.

C/C++의 특별한 기능, 특성(features)을 활용하는 것은 아니고 제공된 함수를 사용하는 것이므로 C/C++에 익숙지 않아도 쉽게 할 수 있다. 그리고 CSE를 전공한다면 당연히 C/C++로도 만들 수 있어야 하겠죠?